Before the availability of the personal computer (PC), computer graphics packages were expensive tools primarily reserved for industrial applications. Early microcomputers were only capable of rendering simple line drawings with a low screen resolution (256.times.256, for example). As microcomputers evolved, higher resolution color displays became available, and software applications routinely provided data output in a graphical manner. The graphics techniques used were unstructured, with objects defined in terms of absolute coordinates using straight lines. Subsequently, graphics "primitives" were used, enabling circles, ellipses, rectangles and polygons to be drawn with a single instruction. The use of primitives that can be rendered with a single instruction set of parameters has increased the speed at which the images can be rendered.
The availability of computer graphics has generated a demand for higher resolutions and three dimensional (3-D) rendering capabilities. Computer animation and games, in particular, have spawned a revolution in computer graphics capabilities. A 3-D image can be represented in a computer system as a collection of graphical objects, such as polygons, lines, and points. A set of vertex points defines a polygon. Associated with each point are certain pixel values, such as shading, texturing, color, and the like. Identification of other points within the polygon typically is done through the use of linear interpolation. Once interpolated, the polygon can be rendered on a computer monitor by successive scanning of orthogonal rows of the polygon.
Performing the linear interpolation calculations for each point (or pixel) of the polygon is very processor intensive. To minimize computations, polygon rendering typically is performed using a forward (or main) slope technique. Referring to the example of FIG. 6, a polygon 40 is divided into two adjacent triangles 47 and 49. The main slope technique requires the calculation of a main slope value (.DELTA. main) which defines the slope of the side 45 that extends the entire vertical length of the triangle 40. Two opposite slopes are determined which represent the slopes of the other two sides 51, 53 of the triangle. A width slope value (.DELTA. width) is calculated to define the incremental change in width for each successive orthogonal scan line (or row) of the polygon. An initial width value is provided for each triangle 47, 49 to represent the width of the first orthogonal scan for that triangle. Polygon 40 may also include depth values (or z values). An initial x and y value (x.sub.1, y.sub.1) defines the location of the initial vertex for the polygon, while the z value (z.sub.1) defines the depth. The z value is used to determine whether the image being rendered is in front of or behind other images, and thus determines whether the image will appear on the display, or whether it will be "hidden" behind another object. Other initial and slope values also may be generated to render the polygon, such as initial values for red, blue and green initial, and main and ortho slope values defining incremental variations in each color in both the x and y directions. Each of the triangles 47, 49 also has an associated count value to represent the number of scan lines required to render each triangle. In the preferred embodiment, the count value is determined by the y coordinate values of the vertex points. Thus, the upper count (COUNT 0) is found by subtracting y.sub.2 from y.sub.1. Similarly, the lower count value is determined by subtracting y.sub.3 from Y.sub.2.
Each of the various initial and slope values typically are defined by a software graphics application driver, running on the host processor. Thus, the software driver, through the vehicle of the host processor, generates a "display list" of parameters that are written to the graphics controller or processor. These parameters include, for example, the initial and slope values identified above. The graphics controller then uses the display list values in generating the graphics to be displayed.
In addition to the basic position and color parameters, graphics controllers are available which permit the texture of the polygon to be represented as part of the display. A texture may be defined as an image of a pattern generated by the software driver. Graphics controllers perform texture mapping by taking the pattern, which represents a flat image, and mapping the pattern in a curved or contoured manner. Thus, for example, the graphics application may require a particular pattern mapped to a teapot, or some other three dimensional object. In that case, the flat pattern image would be mapped to the teapot to represent the curved surface of the teapot, thus giving the illusion that the teapot is a three dimensional object.
When rendering in a three dimensional (3D) graphics application, such as a 3D animation application, a difficulty arises because the object moves. If the animation depicts relative movement of the object with respect to the viewer, (i.e. a person walking past a statue in a courtyard), then the distance between the object (the statue) and the viewer changes. To represent this change in distance, the object is rendered larger or smaller to reflect the viewer moving closer or further from it. To accomplish this type of rendering in 3D animation, different size versions of the object are generated, and a particular size version of the object is selected based upon the distance between the viewer and the object. The various size versions of the object are generated by the software driver by either compressing or expanding the image. Because resolution is lost when converting from a smaller to a larger image, the graphics application typically uses the largest possible image as the base image, so that smaller versions may be made by compressing the base image. Compression of the texture map is done through the use of filtering and averaging algorithms to compress the image. Thus, if the initial image was 512 bytes by 512 bytes (512.times.512), the map could be compressed to 256.times.256, 128.times.128, 64.times.64, or 32.times.32 or 16.times.16, for example, giving six different size images for the same object. Compression of each image is performed by taking a grouping of four pixels and averaging the pixel values to obtain a single pixel value. Each of the different size versions of the image are referred to as "Mip-maps."
In certain instances, several Mip-maps may be used to generate a polygon to provide a desired spatial relationship. Thus, for example, if the polygon being rendered is a brick wall that extends into the distance, it may be desirable to use different Mip-maps for different sections of the wall to make the bricks appear smaller for each section extending in the distance. Thus, initially, a first Mip-map of 256.times.256 may be used to render the first section of the wall. The section of the wall that is further away may then be rendered using a second Mip-map of 128.times.128. Proceeding further down the wall, it may be desirable to use a third Mip-map of 64.times.64. Thus, for objects that extend into the distance, it may be desirable to use different Mip-maps for patterns to add a sense of realism to the graphics display.
For most implementations of Mip-maps, the image is partitioned based upon the mip-maps and each mip-map partitions independently drawn. In addition, a separate set of interpolators and comparators are provided that track the location of the pixel being generated, and switch between Mip-maps based upon pixel location. The use of interpolators and comparators increases the number of gates required to implement the hardware and/or increases the number of clock cycles required to execute the software application. Thus, the interpolators required to switch between Mip-maps add to the overhead involved in generating the graphics display. It would be advantageous if mip-maps could be switched without the necessity of an inordinate number of additional gates.
In addition, it would be advantageous if the polygon could be rendered without breaking it into smaller polygons corresponding to the different Mip-maps. Partitioning the polygon into multiple sections and rendering these sections individually greatly increases the amount of time required to render the object. Instead, it would be advantageous if the object could be rendered with a single instruction by dynamically switching from one Mip-map to another without dissecting the object.